When a computer application provides data to a device for printing and/or display, an intermediate description of the page is often given to the device driver software in a page description language, such as PostScript or PCL, which provide descriptions of the objects to be rendered onto the page, rather than a raster image to be printed. Equivalently, a set of descriptions of graphics objects may be provided in function calls to a graphics interface, such as the Microsoft Windows GDI, or Unix's X-11. The page is typically rendered for printing and/or display by an object-based graphics system (or Raster Image Processor).
Most of these object based graphics systems utilize a large area of memory, known to the art as a frame store or a page buffer, to hold a pixel-based image of the page or screen for subsequent printing and/or display. Typically, the outlines of the graphic objects are calculated, filled and written into the frame store. For two-dimensional graphics, objects that appear in front of other objects are simply written into the frame store after the background objects, thereby replacing the background on a pixel by pixel basis. This is commonly known to the art as “Painter's algorithm”. Objects are considered in priority order, from the rearmost object to the foremost object, and typically, each object is rasterized in scanline order and pixels are written to the framestore in sequential runs along each scanline. Some graphics interfaces allow a logical or arithmetic operation to be specified, to be performed between one or more graphics objects and the already rendered pixels in the frame buffer. In these cases the principle remains the same: objects (or groups of objects) are rasterized in scanline order, and the result of the specified operation is calculated and written to the framestore in sequential runs along each scanline.
There are essentially two problems with this technique. The first is that it requires fast random access to all of the pixels in the framestore. This is because each new object could affect any pixel in the frame store. For this reason, the frame store is normally kept in semiconductor random access memory (RAM). For high-resolution color printers the amount of RAM required is very large, typically in excess of 100 Mbytes, which is costly and difficult to run at high speed. The second problem is that many pixels, which are painted (rendered), are over-painted (re-rendered) by later objects. Painting these pixels with the earlier objects is a waste of time.
One method for overcoming the large frame-store problem is the use of “banding”. When banding is used, only part of the framestore exists in memory at any one time. All of the objects to be drawn are retained in a “display list”, which is an internal representation of the information required to draw the objects on the page. The display list is considered in object order as above, and only those pixel operations which fall within the fraction of the page which is held in the band are actually performed. After all objects in the display list have been drawn, the band is sent to the printer (or to intermediate storage) and the process is repeated for the next band of the page. There are some penalties with this technique, however. For example, the objects being drawn must be reconsidered many times, once for each band. As the number of bands increases, so does the repetitious examination of the objects requiring rendering. Also, the technique of banding does not solve the problem of the cost of over-painting.
Some other graphic systems consider the image in scan line order. Again, all of the objects on the page are retained in a display list. On each scanline the objects which intersect that scanline are then considered in priority order and for each object, spans of pixels between the intersection points of the object edges with the scanline are filled in a line store. This technique overcomes the large framestore problem, however it still suffers from the over-painting problem.
Other graphic systems utilise pixel-sequential rendering to overcome both the large framestore problem and the over-painting problem. In these systems, each pixel is generated in raster order. Again, all objects to be drawn are retained in a display list. On each scan line, the edges of objects, which intersect that scanline, are held in increasing order of their intersection with the scan line. These points of intersection, or edge crossings, are considered in turn, and used to toggle an array of fields that indicate the activity of the objects in the display list. There is one activity field for each object painting operation that is of interest on the scan line. There is also a field to indicate operations that do not require previously generated data. Between each pair of edges considered, the color data for each pixel, which lies between the first edge and the second edge, is generated by using a priority encoder on the activity flags to determine which operations are required to generate the color, and performing only those operations for the span of pixels between the two edges. In preparation for the next scanline, the coordinate of intersection of each edge is updated in accordance with the nature of each edge, and the edges are sorted into increasing order of intersection with that scanline. Any new edges are also merged into the list of edges.
Graphic systems which use pixel-sequential rendering have significant advantages in that there is no frame store or line store, no unnecessary over-painting, and the object priorities are dealt with in constant order time by the priority encoder, rather than in order N time, where N is the number of priorities.
However, it is still often necessary to perform several compositing operations to combine color from several different objects into a rendered pixel, and this can form a significant bottleneck in the overall rendering process.